package 全排列;


import java.util.*;

/**
 * Created by hest0 on 2017/4/21.
 */
public class 全排列注释版 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            ArrayList<String> permutation = Permutation(sc.next());
            for (String x : permutation)
                System.out.println(x);
        }
        sc.close();
    }

    private static ArrayList<String> Permutation(String str) {
        //输入
        ArrayList<String> al = new ArrayList<>();
        if (str == null || str.length() == 0 || str.length() > 9)
            return al;
        ArrayList<String> sal = str2al(str);

        //计算全排列
        ArrayList<ArrayList<String>> Perm = calPerm(sal);

        //转成成目标需要的输出
        for (int i = 0; i < Perm.size(); i++) {
            al.add(al2str(Perm.get(i)));
        }

        //去重，字典排序
        HashSet<String> hs = new HashSet<>(al);
        ArrayList<String> res = new ArrayList<>(hs);
        Collections.sort(res);
        return res;
    }

    //重构计算全排列的代码
    private static ArrayList<ArrayList<String>> calPerm(ArrayList<String> sal) {
        ArrayList<ArrayList<String>> tal = new ArrayList<>();
        calPermRecursion(tal, sal, 0);
        return tal;
    }

    //计算全排列递归，计算全排列最黑心的代码
    //算法：从小到大的递归n--->[0，sal.size]
    //输入：ArrayList，由基本元素组成的
    //输出：ArrayList<ArrayList<String>>，内部是基本元素组成的
    private static void calPermRecursion(ArrayList<ArrayList<String>> tal, ArrayList<String> sal, int n) {
        if (n == sal.size()) {
            tal.add(new ArrayList<>(sal));
        } else {
            for (int i = n; i < sal.size(); i++) {
                Collections.swap(sal, i, n);
                calPermRecursion(tal, sal, n + 1);
                Collections.swap(sal, i, n);
            }
        }
        System.out.println(tal.toString());
    }

    //将输入的串转化成基本元素
    private static ArrayList<String> str2al(String s) {
        ArrayList<String> al = new ArrayList<>();
        for (int i = 0; i < s.length(); i++)
            al.add(String.valueOf(s.charAt(i)));
        return al;
    }

    //讲输出的ArrayList<ArrayList<String>>中的内部ArrayList<String>转化成目标的串
    private static String al2str(ArrayList<String> al) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < al.size(); i++)
            sb.append(al.get(i));
        return sb.toString();
    }
}
